package Algorithm.Dp;

import java.util.HashMap;
import java.util.Map;

//https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/
//873. 最长的斐波那契子序列的长度
public class Leetcode873_最长的斐波那契子序列的长度 {
    class Solution {
        public int lenLongestFibSubseq(int[] arr) {
            int n = arr.length;
            Map<Integer, Integer> index = new HashMap();
            for(int i = 0;i < n;i++){
                index.put(arr[i], i);
            }

            Map<Integer, Integer> longest = new HashMap();
            int ans = 0;
            for(int k = 0;k < n;k++){
                for(int j = 0; j < k; j++){
                    int i = index.getOrDefault(arr[k] - arr[j], -1);
                    if(i >= 0 && i < j){
                        int cand = longest.getOrDefault(i * n + j, 2) + 1;
                        longest.put(j * n + k, cand);
                        ans = Math.max(ans, cand);
                    }
                }
            }

            return ans >= 3 ? ans : 0;
        }
    }
}
